package com.leetcode.sort.basic_sort;

/**
 * @author Dennis Li
 * @date 2020/9/10 0:59
 */
public class HeapSort extends Sort {

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            int[] res = {5, 13, 9, 2, 3, 19};
            sort(res);
            System.out.println(isSorted(res));
        }
    }

    // 自顶向下
    public static void sortUpToDown(int[] arr) {
        buildHeap(arr);

        for (int i = arr.length - 1; i >= 0; i--) {
            // 将最大的节点放到最后面
            swap(arr, 0, i);
            // 排除最后一个结点，进行下沉堆化
            heapify3(arr, 0, i);
        }

    }

    private static void heapify3(int[] tree, int i, int n) {
        if (i >= n) {
            return;
        }

        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;

        int max = i;

        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }

        if (max != i) {
            swap(tree, i, max);
            heapify3(tree, max, n);
        }
    }

    private static void buildHeap(int[] tree) {
        int lastNode = tree.length - 1;
        int parent = (lastNode - 1) >> 1;

        for (int i = parent; i >= 0; i--) {
            heapify3(tree, i, tree.length);
        }
    }

    private static void sort(int[] nums) {
        buildHeap2(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            swap(nums, 0, i);
            heapify2(nums, 0, i);
        }
    }

    private static void heapify2(int[] nums, int i, int n) {
        if (i >= n)
            return;

        int max = i;
        int c1 = i * 2 + 1;
        int c2 = i * 2 + 2;

        if (c1 < n && nums[max] < nums[c1])
            max = c1;
        if (c2 < n && nums[max] < nums[c2])
            max = c2;

        if (max != i) {
            swap(nums, i, max);
            heapify2(nums, max, n);
        }
    }

    private static void buildHeap2(int[] nums) {
        int lastNode = nums.length - 1;
        int parent = (lastNode - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify2(nums, i, nums.length);
        }
    }

    // 时间 O(nlogn) 空间O(1)
    static class Practice extends Sort {

        public static void main(String[] args) {
            for (int i = 0; i < 10; i++) {
                int[] nums = generateArray();
                sort(nums);
                System.out.println(isSorted(nums));
            }
        }

        public static void sort(int[] nums) {
            buildHeap(nums);
            for (int i = nums.length - 1; i >= 0; i--) {
                swap(nums, 0, i);
                heapify(nums, 0, i);
            }
        }

        private static void buildHeap(int[] nums) {
            int lastNode = nums.length - 1;
            int parent = (lastNode - 1) / 2;
            for (int i = parent; i >= 0; i--) {
                heapify(nums, i, nums.length);
            }
        }

        private static void heapify(int[] nums, int i, int n) {
            while (i < n) {
                int max = i, c1 = i * 2 + 1, c2 = i * 2 + 2;
                if (c1 < n && nums[max] < nums[c1]) max = c1;
                if (c2 < n && nums[max] < nums[c2]) max = c2;
                if (i == max) break;
                swap(nums, i, max);
                i = max;
            }
        }

    }

}
